package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC96 {

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 这个题目真是非常难了，非常非常难想到dp
     * 参考文档：https://www.cnblogs.com/grandyang/p/4299608.html
     * @return:
     */

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }

    public int numTreesRecur(int n) {
        if (n <= 1) return 1;

        int count = 0;
        for (int i = 0; i < n; i++) {
            int lc = numTreesRecur(i);
            int lr = numTreesRecur(n - 1 - i);
            count += lc * lr;
        }

        return count;
    }

    public static void main(String[] args) {
        LC96 an = new LC96();
        int n = 5;
        System.out.println(an.numTrees(5));
        System.out.println(an.numTreesRecur(5));
    }
}
